#include "path.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>


#define X_SIZE 9  // X轴有9格 (0 到 8)
#define Y_SIZE 7  // Y轴有7格 (0 到 6)


// 全局变量
int map[Y_SIZE][X_SIZE];     // 地图：0=可通过, 1=禁飞区
int visited[Y_SIZE][X_SIZE]; // 访问标记
int path[100][2];           // 存储路径序列，假设最大1000步
int path_index = 0;          // 当前路径步数

int forbid_x1 = 1, forbid_x2 = 1, forbid_x3 = 1; // 设置禁飞区x坐标
int forbid_y1 = 0, forbid_y2 = 1, forbid_y3 = 2; // 设置禁飞区y坐标
static int dist[Y_SIZE][X_SIZE];
static int parentY[Y_SIZE][X_SIZE];
static int parentX[Y_SIZE][X_SIZE]; // 记录路径
static int pathToTarget[100][2];
// 用于BFS的队列
typedef struct {
    int x, y;
    int dist; // 距离
} QueueNode;

QueueNode queue[100];
int q_front, q_rear;



// 初始化队列
void initQueue() {
    q_front = q_rear = 0;
}

// 入队
void enqueue(int x, int y, int dist) {
    queue[q_rear].x = x;
    queue[q_rear].y = y;
    queue[q_rear].dist = dist;
    q_rear++;
}

// 出队
QueueNode dequeue() {
    return queue[q_front++];
}

// 检查队列是否为空
int isQueueEmpty() {
    return q_front == q_rear;
}

// 从用户输入设置禁飞区
void setObstaclesFromInput() {
    // 清空地图
    for (int y = 0; y < Y_SIZE; y++) {
        for (int x = 0; x < X_SIZE; x++) {
            map[y][x] = 0;
            visited[y][x] = 0;
        }
    }
    map[forbid_y1][forbid_x1] = 1;
    map[forbid_y2][forbid_x2] = 1;
    map[forbid_y3][forbid_x3] = 1;
    
}

// 记录移动到新位置
void moveTo(int x, int y) {
    path[path_index][0] = x;
    path[path_index][1] = y;
    path_index++;
}

// 使用BFS找到从 (startX, startY) 到 (targetX, targetY) 的最短路径，并执行行走
// 返回 1 如果找到路径并成功行走，0 如果目标不可达
int walkToTarget(int startX, int startY, int targetX, int targetY) {
    if (startX == targetX && startY == targetY) {
        // 已经在目标点
        moveTo(startX, startY); // 记录当前位置
        return 1;
    }

    // 检查目标点是否可通过
    if (map[targetY][targetX] == 1) {
        return 0;
    }

    // BFS 初始化
//    int dist[Y_SIZE][X_SIZE];
//    int parentY[Y_SIZE][X_SIZE], parentX[Y_SIZE][X_SIZE]; // 记录路径
    int i, j;
    for (i = 0; i < Y_SIZE; i++) {
        for (j = 0; j < X_SIZE; j++) {
            dist[i][j] = INT_MAX;
            parentY[i][j] = -1;
            parentX[i][j] = -1;
        }
    }

    initQueue();
    dist[startY][startX] = 0;
    enqueue(startX, startY, 0);

    int dx[] = { 1, -1, 0, 0 };
    int dy[] = { 0, 0, 1, -1 };

    int found = 0;
    while (!isQueueEmpty()) {
        QueueNode current = dequeue();
        int x = current.x;
        int y = current.y;

        if (x == targetX && y == targetY) {
            found = 1;
            break;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < X_SIZE && ny >= 0 && ny < Y_SIZE && map[ny][nx] == 0) {
                if (dist[ny][nx] == INT_MAX) {
                    dist[ny][nx] = dist[y][x] + 1;
                    parentX[ny][nx] = x;
                    parentY[ny][nx] = y;
                    enqueue(nx, ny, dist[ny][nx]);
                }
            }
        }
    }

    if (!found) {
        return 0;
    }

    // 重构路径 (从目标到起点)
//    int pathToTarget[100][2];
    int steps = 0;
    int tx = targetX, ty = targetY;
    while (tx != startX || ty != startY) {
        pathToTarget[steps][0] = tx;
        pathToTarget[steps][1] = ty;
        steps++;
        int px = parentX[ty][tx];
        int py = parentY[ty][tx];
        tx = px;
        ty = py;
    }
    // 添加起点
    pathToTarget[steps][0] = startX;
    pathToTarget[steps][1] = startY;
    steps++;

    // 反向遍历路径 (从起点到目标) 并执行行走
    for (int i = steps - 1; i >= 0; i--) {
        int x = pathToTarget[i][0];
        int y = pathToTarget[i][1];
        // 只有当不是当前位置时才移动（避免重复记录起点）
        if (i < steps - 1 || (x != startX || y != startY)) {
            moveTo(x, y);
            visited[y][x] = 1; // 标记为已访问
        }
    }

    return 1;
}

// 检查坐标是否合法（在地图范围内且非禁飞区）
int isValidCoordinate(int x, int y) {
    return (x >= 0 && x < X_SIZE && y >= 0 && y < Y_SIZE && map[y][x] == 0);
}

// 检查是否还有未访问的非禁飞区点，并找到离 (fromX, fromY) 最近的一个
// 返回 1 如果找到，通过 nearestX, nearestY 返回坐标；返回 0 如果没有
int findNearestUnvisited(int fromX, int fromY, int* nearestX, int* nearestY) {
    int minDist = INT_MAX;
    int found = 0;

    for (int y = 0; y < Y_SIZE; y++) {
        for (int x = 0; x < X_SIZE; x++) {
            if (map[y][x] == 0 && !visited[y][x]) {
                int dist = abs(x - fromX) + abs(y - fromY); // 曼哈顿距离
                if (dist < minDist) {
                    minDist = dist;
                    *nearestX = x;
                    *nearestY = y;
                    found = 1;
                }
            }
        }
    }
    return found;
}

// 遍历所有可达的非禁飞区点
int traverseAllReachable(int startX, int startY) {
    int currentX = startX, currentY = startY;
    int nextX, nextY;
    int allVisited = 0;

    // 首先，确保起点被访问
    if (map[currentY][currentX] == 0) {
        moveTo(currentX, currentY);
        visited[currentY][currentX] = 1;
    }
    else {
      
        return 0;
    }

    // 循环：只要还有未访问的非禁飞区点，就找到最近的并走过去
    while (findNearestUnvisited(currentX, currentY, &nextX, &nextY)) {
        if (walkToTarget(currentX, currentY, nextX, nextY)) {
            currentX = nextX;
            currentY = nextY;
        }
        else {
            // 无法到达下一个点，但可能还有其他可到达的点
            break;
        }
    }

    // 检查是否所有可达点都被访问
    int totalFree = 0, visitedFree = 0;
    for (int y = 0; y < Y_SIZE; y++) {
        for (int x = 0; x < X_SIZE; x++) {
            if (map[y][x] == 0) {
                totalFree++;
                if (visited[y][x]) {
                    visitedFree++;
                }
            }
        }
    }

    if (visitedFree == totalFree) {
       
        allVisited = 1;
    }
    else {
       
        allVisited = 0;
    }

    return allVisited;
}

void path_design_init()
{
  path_index = 0;
memset(path, 0, sizeof(path));
memset(visited, 0, sizeof(visited));
	int startX, startY, endX, endY;

int flag_forbid_x = 0;
int flag_forbid_y = 0;
startX = 0;
startY = 0;
if (forbid_x1 == forbid_x2 && forbid_x1 == forbid_x3)
{
    flag_forbid_x = 1;
}
else if (forbid_y1 == forbid_y2 && forbid_y1 == forbid_y3)
{
    flag_forbid_y = 1;
}
if (flag_forbid_x == 1)
{
    if (forbid_x1 >= 1)
    {
        endX = 0;
        endY = 3;
    }
    else
    {
        endX = 3;
        endY = 0;
    }
}
else if (flag_forbid_y == 1)
{
    if (forbid_y1 >= 1)
    {
        endX = 3;
        endY = 0;
    }
    else
    {
        endX = 0;
        endY = 3;
    }
}
setObstaclesFromInput();

// 1. 从起点开始遍历所有可达的非禁飞区点
int traversalSuccess = traverseAllReachable(startX, startY);

// 获取当前位置（遍历后的最后位置）
int currentX = (path_index > 0) ? path[path_index - 1][0] : startX;
int currentY = (path_index > 0) ? path[path_index - 1][1] : startY;

//// 2. 从当前位置移动到终点
//int endReached = 0;
//if (currentX == endX && currentY == endY) {
//    endReached = 1;
//}
//else {
//    endReached = walkToTarget(currentX, currentY, endX, endY);
//}

}


